import java.util.Arrays;

public class HeapKTest {
    public static void main(String[] args) {
        int[] a=new int[]{3,1,2,7,33,12,3,2,4,5,6};
        HeapKTest hkt=new HeapKTest();
        System.out.println(Arrays.toString(hkt.topK(a,5)));
    }

    public int[] topK(int[] nums,int k){
        if(nums.length==0||k>nums.length)
            return new int[0];
        int[] heap=Arrays.copyOfRange(nums,0,k);
        buildHeap(heap);
        for(int i=k;i<nums.length;i++){
            if(heap[0]>nums[i]){
                heap[0]=nums[i];
                adjustHeap(heap,0,heap.length);
            }
        }
        heapSort(heap);
        return heap;
    }

    private void buildHeap(int[] heap){
        int lastNonleaf=heap.length/2-1;
        while(lastNonleaf>=0){
            adjustHeap(heap,lastNonleaf,heap.length);
            lastNonleaf--;
        }
    }

    private void adjustHeap(int[] heap,int index,int len){
        int temp=heap[index];
        for(int k=index*2+1;k<len;k=k*2+1){
            if(k+1<len&&heap[k+1]>heap[k]){
                k++;
            }
            if(heap[k]>temp){
                swap(heap,k,index);
                index=k;
            }else break;
        }
    }

    private void heapSort(int[] heap){
        for(int i=heap.length-1;i>=0;i--){
            swap(heap,0,i);
            adjustHeap(heap,0,i);//因为不会取到这个length，见adjustHeap
        }
    }

    private void swap(int[] nums, int i, int j) {
        nums[i] = nums[i] + nums[j] - (nums[j] = nums[i]);
    }



}
